﻿#include"Allsort.h"
#include <iomanip>
/*
交换函数
*/
void Allsort::swap(int *list, int low, int high)
{
	int temp = list[low];
	list[low] = list[high];
	list[high] = temp;
}

/*
小于函数
*/
bool Allsort::islow(const int low, const int high)
{
	if (low < high)
		return true;
	else
		return false;
}
/*
冒泡排序（稳定）
原理：第一次的内部for循环从记录数组的底部比较到顶部，比较相邻的值。
如果低序号的值比高序号的值大，则二者交换顺序
代价是n2
冒泡排序arr[n]不参与排序*/
void Allsort::BubbleSort(int arr[], int size)
{
	if (!BUBBLE_SORT)
		return;

	bool exchange;
	for (int i = 0; i < size; i++)
	{
		exchange = false;
		for (int j = size - 1; j>i; j--)
		{
			if (arr[j] <arr[j - 1])
			{
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
				exchange = true;
			}
		}

		if (exchange == false)
		{
			return;
		}

	}
}

/*
快速排序(不稳定)
原理：首先选择一个轴值，小于轴值的结点被放到轴值的左边，大于轴值的结点被放到轴值的右边，这样轴值就被放在了正确的位置上。
然后对轴值左边和右边的子序列进行类似操作。
第一次调用的形式为Quicksort(list,0,n-1)
代价是n*logn
*/

void Allsort::QuickSort(int A[], int startingsub, int endingsub)
{
	if (!QUICK_SORT)
		return;

	if (startingsub >= endingsub) return;

	int left = startingsub -1;
	int right = endingsub;
	int nTemp = A[endingsub];

	do
	{
		while (A[++left]< nTemp && left < right);
		while (right != 0 && A[--right] >nTemp);
		if (left < right){
			swap(A, left, right);

		}
	} while (left < right);
	swap(A, left, endingsub);

	QuickSort(A, startingsub, left - 1);
	QuickSort(A, left + 1, endingsub);

	
}

/*
插入排序函数,从小到大,改进过，效率较慢
*/
void Allsort::InsertionSort(int L[],int n)
{
	if (!INSERT_SORT_0)
		return;

	int i, j;
	for (i = 1; i < n; ++i)
	{
		for (j = i - 1; j >= 0 && L[j]>L[j + 1]; --j)
		{
			swap(L, j, j+1);
		}
	}
}

void Allsort::Insertsort1(int a[], int n)
{
	if (!INSERT_SORT_1)
		return;

	int i, j;
	for (i = 1; i < n; i++)
	if (a[i] <a[i - 1])
	{
		int temp = a[i];
		for (j = i - 1; j >= 0 && a[j]>temp; j--)
			a[j + 1] = a[j];
		a[j + 1] = temp;
	}
}


/*
shell排序（不稳定）
原理：将序列分成子序列，然后分别对子序列用插入排序的方法进行排序，最后将子序列组合起来。
代价是n的1.3次幂
*/
void Allsort::Shellsort(int L[], int n)
{
	if (!SHELL_SORT_0)
		return;

	int i, j, gap;
	for (gap = n / 2; gap > 0; gap /= 2)
	{
		for (j = gap; j < n; ++j)
		{
			if (L[j] < L[j - gap])
			{
				int temp = L[j];
				int k = j - gap;
				while (k >= 0 && L[k]>temp)
				{
					L[k + gap] = L[k];
					k -= gap;
				}
				L[k + gap] = temp;
			}
		}
	}
}

void Allsort::ShellsortSimple(int L[], int n)
{
	if (!SHELL_SORT_1)
		return;

	int i, j, gap;
	for (gap = n / 2; gap > 0; gap /= 2)
	for (i = gap; i < n; i++)
	for (j = i - gap; j >= 0 && L[j] > L[j + gap]; j -= gap)
		swap(L,j, j + gap);
}

void Allsort::CountingSort(int L[], int n)
{

}

int Allsort::getDigit(int num, int dig)
{
	return 0;
}

void Allsort::RadixSort(int L[], int left, int right, int d)
{

}


void Allsort::printArray(const int Array[], int arraySize,  int flag)
{
	if (!IS_PRINT || !flag)
		return;

	for (int i = 0; i < arraySize; i++) {
		cout << setw(5)<< Array[i] << " ";
		if (i % 20 == 19)
			cout << endl;
	}
	cout << endl;
}
